// https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

// 题干：给你一个整数数组 nums 和一个整数 x 。
//       每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。
//       请注意，需要 修改 数组以供接下来的操作使用。
//       如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

// 示例：输入：nums = [1,1,4,2,3], x = 5
//       输出：2

// 碎语：正难则反，则我们可以求中间一段连续的数组，也就是子串，其所有值的和为sum-x
//       原题要求最少操作数，则我们可以求最长子串的长度
//       并且，其数组中的所有元素皆为正数，可以考虑滑窗

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int sumAll = accumulate(nums.begin(), nums.end(), 0);
        int left = 0, right = 0, sum = 0, subMax = INT_MIN;

        // target = sumAll - x
        // 如果target小于0，则直接返回，且其与循环逻辑不符合
        if (sumAll - x < 0) return -1;
        while (right < nums.size()){
            sum += nums[right]; // 入窗

            // 若和大于sumAll-x，则进入循环
            while (sum > sumAll - x){
                sum -= nums[left++];
            }
            // 出循环，此时sum<=sumAll-x，判断一下是否相等，如果是，更新结果
            if (sum == sumAll - x) subMax = max(subMax, right - left + 1);
            right++;
        }

        return subMax == INT_MIN ? -1 : nums.size() - subMax;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,1};

    cout << sol.minOperations(nums, 3) << endl;


    return 0;
}